#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

//O(N^3)
int maxSubArraySum1(int * array, int n) {
	int max = INT_MIN;

	for(int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			int sum = 0;
			for (int k = i; k <= j; ++k)
				sum += array[k];
			if (sum > max)
				max = sum;
		}
	}

	return max;
}

//O(N^2)
int maxSubArraySum2(int * array, int n) {
	int max = INT_MIN;
	
	for(int i = 0; i < n; ++i) {
		int sum = 0;
		for(int j = i; j < n; ++j) {
			sum += array[j];
			if (sum > max)
				max = sum;
		}
	}

	return max;
}

//recursive; O(Nlog(N))
#define max(a, b) ((a<b)?b:a)
int maxSubArraySum3_helper(int * array, int start, int end) {
	if (start > end)
		return 0;
	if (start == end)
		return array[start];

	int m1 = maxSubArraySum3_helper(array, start, start + (end-start)/2);
	int m2 = maxSubArraySum3_helper(array, start + (end-start)/2 + 1, end);

	int sum1 = 0, max1 = INT_MIN;
	int sum2 = 0, max2 = INT_MIN;
	for (int i = start + (end-start)/2; i >= start; --i) {
		sum1 += array[i];
		if (sum1 > max1)
			max1 = sum1;
	}
	for (int i = start + (end-start)/2 + 1; i <= end; ++i) {
		sum2 += array[i];
		if (sum2 > max2)
			max2 = sum2;
	}

	return max(max(m1,m2), max1+max2);
}

int maxSubArraySum3(int * array, int n) {
	return maxSubArraySum3_helper(array, 0, n - 1);
}

//dp:O(N)
int maxSubArraySum4(int * array, int n) {
	int * all = (int *)malloc(sizeof(int) * n);
	int * start = (int *)malloc(sizeof(int) * n);
	
	all[n-1] = array[n-1];	//for elements from i to n-1, the max sub array sum of elements
	start[n-1] = array[n-1];	//for elements from i to n-1, the max sub array sum starting from element i
	for (int i = n - 2; i >= 0; i--) {
		start[i] = max(array[i], array[i]+start[i+1]);
		all[i] = max(start[i], all[i+1]);
	}
	
	int ret = all[0];
	free(all);
	free(start);
	return ret;
}

//dp:O(N), O(1) space complexity
int maxSubArraySum5(int * array, int n) {
	
	int all = array[n-1];	//for elements from i to n-1, the max sub array sum of elements
	int start = array[n-1];	//for elements from i to n-1, the max sub array sum starting from element i
	for (int i = n - 2; i >= 0; i--) {
		start = max(array[i], array[i]+start);
		all = max(start, all);
	}
	
	return all;
}

int main() {
	int array[10] = {1, -2, 3, 10, -4, 7, 2, -5};
	printf("maxSubSum: %d\n", maxSubArraySum1(array, 10));
	printf("maxSubSum: %d\n", maxSubArraySum2(array, 10));
	printf("maxSubSum: %d\n", maxSubArraySum3(array, 10));
	printf("maxSubSum: %d\n", maxSubArraySum4(array, 10));
	printf("maxSubSum: %d\n", maxSubArraySum5(array, 10));
	return 0;
}
